package com.cat.chapter035;

import java.util.ArrayList;
import java.util.HashMap;

/**
*   @description https://leetcode.cn/problems/maximum-frequency-stack/
*   @author cat
*   @create 2025/6/6 17:46
*   @since JDK17
*/

public class FreqStack {
    private int cnt = 0;
    private HashMap<Integer, Integer> hashMap;
    private HashMap<Integer, ArrayList<Integer>> stack;

    public FreqStack() {
        stack = new HashMap<>();
        stack.put(0, new ArrayList<>());
        hashMap = new HashMap<>();
    }

    public void push(int val) {
        if (hashMap.containsKey(val)) { // 存在
            Integer last = hashMap.get(val);
            hashMap.put(val, last + 1); // 加一
        } else {
            hashMap.put(val, 1);
        }

        Integer times = hashMap.get(val);   // 拿到有多少个
        if (times > cnt) {   // 最大频率增加
            cnt = times;
            ArrayList<Integer> list = new ArrayList<>();
            list.add(val);
            stack.put(cnt, list);
            return;
        }
        ArrayList<Integer> list = stack.get(times);
        list.add(val);
    }

    public int pop() {
        ArrayList<Integer> list = stack.get(cnt);   // 拿到最高层
        Integer last = list.remove(list.size() - 1);   // 拿到最后一个
        hashMap.put(last, cnt - 1);
        if (list.isEmpty()) {   // 这一层都没有了
            stack.remove(cnt);  // 删除这一层
            cnt--;  // 最高层减少
        }
        return last;
    }
}
